package num236;

/**
 * @author : DuJiabao
 * @Date : 2021/2/6 17:51
 * @Project : sword-finger-offer
 * @File : null.java
 * @Desc :236. 二叉树的最近公共祖先
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
 *
 * 解法： 最近的公共结点，p和q一定在其左右两边。
 * 因此，递归查找左边和右边，
 * 如果左边为空，右边不为空，就返回右边的内容，说明p和q都在右边，公共结点也在右边
 * 如果右边为空，左边不为空，则返回左边的内容，说明其左边。
 * 如果左右都不为空，则表示p和q就在这个节点，就把该结点向上传。
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else {
            return root;
        }
    }
}
